package com.itHsuDS.recursion;

public class Queen8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组arr，保存皇后放置位置的结果，比如arr={0,4，7,5，2，6，1,3}
    int[] arr = new int[max];

    static int count=0;
    public static void main(String[] args) {
        Queen8 queen8=new Queen8();
        queen8.check(0);
        System.out.println(count);
    }

    //放置第n个皇后
    //特别注意：check 是每一次递归时，进入到check中都有 for (int i = 0; i < max; i++) 因此会有回溯
    private void check(int n) {
        if (n == max) {//n==8时，前面8个皇后已经放好了，因为n从0开始，此时已经是第9个了
            print();
            return;
        }
        //依次放入，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前皇后n，放到该行的第一列
            arr[n] = i;
            //判断当放置皇后n到第i列是否冲突
            if(judge(n)){//成立说明不冲突
                //接着放（n+1）个，递归
                check(n+1);
            }
            //如果冲突就会继续执行 arr[n]=i；即将第n个皇后放在本行后移的一个位置
        }
    }

    /**
     * 查看当我们放第n个皇后时检测该皇后是否和前面已经摆放的皇后冲突
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        //将n前面的皇后检测
        for (int i = 0; i < n; i++) {
            // 1、 arr[i]==arr[n] 表示判断第n个皇后和前面n-1个皇后是否在同一列
            // 2、 Math.abs(n-i)==Math.abs(arr[n]-arr[i]) 表示判断第n个皇后和第i个皇后是否在同一斜线
            // 3、 这里不需要判断是否在同一行是因为本身n就是递增的，本身就不在同一行摆放
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    //可以将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
